﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.MaxProfit1
{
    /// <summary>
    /// 买股票 动态规划
    /// </summary>
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 7, 1, 5, 3, 6, 4 };
            Console.WriteLine(MaxProfit(nums));
            Console.ReadKey();
        }

        /// <summary>
        /// 双指针(变种)
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public static int MaxProfit(int[] prices)
        {
            int minValue = prices[0];
            int maxValue = -1;
            for (int i = 0; i < prices.Length; i++)
            {
                minValue = Math.Min(minValue, prices[i]);
                maxValue = Math.Max(maxValue, prices[i] - minValue);
            }
            return maxValue;
        }

        /// <summary>
        /// 暴力方法，超时
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public static int MaxProfit1(int[] prices)
        {
            int maxValue = -1;
            for (int i = 0; i < prices.Length; i++)
            {
                for (int j = i; j < prices.Length; j++)
                {
                    int delta = prices[j] - prices[i];
                    if (delta> maxValue)
                    {
                        maxValue = delta;
                    }
                }
            }
            return maxValue;
        }
    }
}
